/**
     *
     * 删数字问题
     *
     * arr = {0, 1, 2, 3, 4, 5, 6, 7}
     *
     * 0->1->2(删除)->3->4-5(删除)->6->7->0(删除)->1->3-4(删除)->6->7->1(删除)->3->6->7(删除)->3->6->3(删除)->6
     *  1,3,4,6,7
     *  1,3,6,7
     *  3,6
     *  6
     *
     *  N个人编号（0〜N-1），报到M的时候自杀，第一个人自杀他的编号为(M-1)%N(限余是为了防止超出)
     *  设F(x) = y,x为人数,y为还存下的人编号
     * 
     * {0,1,2,3,4,5} = pos
     * {1,2,3,4,5,6} = arr
     * 每隔M=3个自杀，N=6个人
     * 每次自杀总是k+(M - 1)%arr.length编号自杀
     * 第一次自杀,pos=2自杀，此时k=3。变换一下数组，从k开始。
     * {0,1,2,3,4} = pos
     * {4,5,6,1,2} 此时k=0
     * 第二次自杀,pos=2,此时k=3。变换一下数组，从k开始。
     * {0,1,2,3} = pos
     * {1,2,4,5} 此时k=0
     * 第三次自杀,pos=2,此时k=3。变换一下数组，从k开始。
     * {0,1,2} = pos
     * {5,1,2} 此时k=0
     * 第四次自杀,pos=2,此时k=0。变换一下数组，从k开始。
     * {0,1} = pos
     * {5,1} 此时k=0
     * 第五次自杀,pos=0,此时k=1。变换一下数组，从k开始。
     * {0} = pos
     * {1} 此时k = 0          可得知最后一次自杀必定是F(1) = 0 pos
     * 
     * 最后一个自杀的一定是被重新编号的0
     * 即：只有一人时F(1)=0
     * F(2)时，先自杀的一定是(M-1)%当前人数n
     * 然后就出现F(n-1)的情况，F(n-1)每次都会自杀的个(M-1)%当前人数，然后变成下一层的情况
     * 直到F(1)=0
     * F(2)情况自杀后变成F(1)的情况，可以看到若求F(2)=(下一层自杀的0 pos+3)%当前人数2
     * 得出在2个人情况下最后自杀的pos
     * 取余是防止超出人数
     * 
     * F(N) = (F(N-1) + M)%N //M表示当前层要走的3步数，F(N-1)表示下层最后一个自杀的步数(相对与本层自杀后的情况)
     * 可以得知通过相对位置再加上本层3步，可以得到本层情况下的最后一个自杀步数
*/

#include <cstdio>

int getLastKillIndex(int nSize, int nStep){

    int result = 0; //N=1
    for(int i = 2; i <= nSize; ++i){
        result = (result + nStep) % i;
    }
    //在推导的时候方便实现编号为0~N-1，实际实现还是按照1~N来编号的
    return result + 1;
}

int main(int argc, char const *argv[])
{
    const int nSize = 6, nStep = 3;
    int result = getLastKillIndex(nSize, nStep);
    printf("size: %d, step: %d, result: %d,\n", nSize, nStep, result);
    return 0;
}